Search

In this paper, we investigate a new problem of optimal placement of multiple finite-size rectangular facilities with known dimensions in the presence of existing rectangular facilities. This problem has applications in facility layout (re)design in manufacturing, distribution systems, services, and electronic circuit design. Three types of facility interactions are considered: between new facilities and existing facilities; between pairs of existing facilities; and between pairs of new facilities. All interactions are serviced through a finite number of input/output points located on the facility boundaries. Travel is assumed to occur according to the rectilinear (or Manhattan) metric and travel through facilities is prohibited. The objective is to find the simultaneous and non-overlapping placement of new facilities, which minimises the total weighted distance (Minisum objective) between the interacting facilities. To arrive at a solution, we divide the feasible region into sub-regions and prove that the candidates for optimal placement of the new facilities can be drawn from the sub-region boundaries. Being a continuous generalisation of the quadratic assignment problem, the solution complexity of this procedure is exponential in the number of new facilities. Our main contribution is the rigorous treatment of an important problem that unifies facility location and layout theories with minisum objective and rectilinear metrics. [ABSTRACT FROM AUTHOR]

A primal quadratic simplex algorithm tailored to the optimization over the vertices of a polytope is presented. Starting from a feasible vertex, it performs either strictly improving or admissible non-deteriorating steps in order to determine a locally optimum basic feasible solution in terms of the quadratic objective function. The algorithm so generalizes over local improvement methods for according applications, including in particular quadratic optimization problems whose feasible solutions correspond to vertices of a 0-1 polytope. Computational experiments for unconstrained binary quadratic programs, maximum cut, and the quadratic assignment problem serve as a proof of concept and underline the importance of a pivoting rule that is able to accept at least a restricted class of degenerate steps. [ABSTRACT FROM AUTHOR]

Identifying the rank of species in a complex ecosystem is a difficult task, since the rank of each species invariably depends on the interactions stipulated with other species through the adjacency matrix of the network. A common ranking method in economic and ecological networks is to sort the nodes such that the layout of the reordered adjacency matrix looks maximally nested with all nonzero entries packed in the upper left corner, called Nestedness Maximization Problem (NMP). Here we solve this problem by defining a suitable cost-energy function for the NMP which reveals the equivalence between the NMP and the Quadratic Assignment Problem, one of the most important combinatorial optimization problems, and use statistical physics techniques to derive a set of self-consistent equations whose fixed point represents the optimal nodes' rankings in an arbitrary bipartite mutualistic network. Concurrently, we present an efficient algorithm to solve the NMP that outperforms state-of-the-art network-based metrics and genetic algorithms. Eventually, our theoretical framework may be easily generalized to study the relationship between ranking and network structure beyond pairwise interactions, e.g. in higher-order networks. Species forming complex ecological or economic ecosystems are organized in hierarchies and the ranks of such species are determined by the adjacency matrix of their interaction network. We introduce a framework to calculate the ranks of species by finding the optimal permutation of rows and columns that makes the adjacency matrix maximally nested. [ABSTRACT FROM AUTHOR]

This document is a special issue of the journal Algorithms, featuring selected papers from the journal's editorial board members from 2022 and 2023. The issue includes 16 research papers covering a range of topics such as game theory, fault detection in cellular networks, optimization algorithms, machine learning, cryptocurrency trading, and more. Each paper presents its own unique research findings and methodologies. The issue aims to showcase the diverse research interests and expertise of the journal's editorial board members. [Extracted from the article]

It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed-integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems. [ABSTRACT FROM AUTHOR]

The India-Japan Lighting company operates three plants in India. These three plants manufacture headlamps and taillights for the automotive industry. This study examines the facility location problem in one of these plants where 12 facilities must be placed in a two-column multi-row cellular layout. The machining sequences for the 20 parts conveyed among the 12 facilities were specified. The Quadratic Assignment Problem (QAP) is classified as an NP-hard problem in large instances. We modelled the specific instance as a QAP and reported the solution obtained by an easily available generalised reduced gradient (GRG) nonlinear solver and the solution obtained from the Gurobi optimiser. The Gurobi optimiser provides an excellent incumbent solution in quick time, but takes exponential time to reduce the duality gap. [ABSTRACT FROM AUTHOR]

This paper proposes a new approach for solving dynamic facility layout problems (DFLP) using a genetic algorithm (GA) enhanced with machine learning techniques, namely clustering algorithms. The proposed course aims to design a robust layout that can adapt to changes in the input parameters. Traditionally, the DFLPs are solved using adaptive methods, i.e., the layout from period to period varies. However, in the robust approach, the layout remains the same throughout the different planning periods. The GA is used for generating the solutions, and the machine learning technique is used to cluster the solutions and select the candidate solution to undergo the local search procedure. The proposed approach is tested on a set of benchmark instances and compared with published approaches. The results show that the proposed approach outperforms the existing approaches in terms of solution quality, robustness, and computational efficiency. [ABSTRACT FROM AUTHOR]

We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees established in a companion paper for Gaussian weights, in this work, we prove the universality of these guarantees for a general correlated Wigner model. In particular, for two Erdős-Rényi graphs with edge correlation coefficient 1 - σ 2 and average degree at least polylog (n) , we show that GRAMPA exactly recovers the latent vertex correspondence with high probability when σ ≲ 1 / polylog (n) . Moreover, we establish a similar guarantee for a variant of GRAMPA, corresponding to a tighter quadratic programming relaxation of the quadratic assignment problem. Our analysis exploits a resolvent representation of the GRAMPA similarity matrix and local laws for the resolvents of sparse Wigner matrices. [ABSTRACT FROM AUTHOR]

Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper, we propose a new spectral method, graph matching by pairwise eigen-alignments (GRAMPA). Departing from prior spectral approaches that only compare top eigenvectors, or eigenvectors of the same order, GRAMPA first constructs a similarity matrix as a weighted sum of outer products between all pairs of eigenvectors of the two graphs, with weights given by a Cauchy kernel applied to the separation of the corresponding eigenvalues, then outputs a matching by a simple rounding procedure. The similarity matrix can also be interpreted as the solution to a regularized quadratic programming relaxation of the quadratic assignment problem. For the Gaussian Wigner model in which two complete graphs on n vertices have Gaussian edge weights with correlation coefficient 1 - σ 2 , we show that GRAMPA exactly recovers the correct vertex correspondence with high probability when σ = O (1 log n) . This matches the state of the art of polynomial-time algorithms and significantly improves over existing spectral methods which require σ to be polynomially small in n. The superiority of GRAMPA is also demonstrated on a variety of synthetic and real datasets, in terms of both statistical accuracy and computational efficiency. Universality results, including similar guarantees for dense and sparse Erdős–Rényi graphs, are deferred to a companion paper. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is an NP-hard problem with a wide range of applications in many real-world applications. This study introduces a discrete rat swarm optimizer (DRSO)algorithm for the first time as a solution to the QAP and demonstrates its effectiveness in terms of solution quality and computational efficiency. To address the combinatorial nature of the QAP, a mapping strategy is introduced to convert real values into discrete values, and mathematical operators are redefined to make then suitable for combinatorial problems. Additionally, a solution quality improvement strategy based on local search heuristics such as 2-opt and 3-opt is proposed. Simulations with test instances from the QAPLIB test library validate the effectiveness of the DRSO algorithm, and statistical analysis using the Wilcoxon parametric test confirms its performance. Comparative analysis with other algorithms demonstrates the superior performance of DRSO in terms of solution quality, convergence speed, and deviation from the best-known values, making it a promising approach for solving the QAP. [ABSTRACT FROM AUTHOR]

Comparing combinatorial optimization problems is a difficult task. They are defined using different criteria and terms: weights, flows, distances, etc. In spite of this apparent discrepancy, on many occasions, they tend to produce problem instances with similar properties. One avenue to compare different problems is to project them onto the same space, in order to have homogeneous representations. Expressing the problems in a unified framework could also lead to the discovery of theoretical properties or the design of new algorithms. This article proposes the use of the Fourier transform over the symmetric group as the tool to project different permutation-based combinatorial optimization problems onto the same space. Based on a previous study (Kondor, 2010), which characterized the Fourier coefficients of the quadratic assignment problem, we describe the Fourier coefficients of three other well-known problems: the symmetric and nonsymmetric traveling salesperson problem and the linear ordering problem. This transformation allows us to gain a better understanding of the intersection between the problems, as well as to bound their intrinsic dimension. [ABSTRACT FROM AUTHOR]

A new method is proposed for robust partial quadratic eigenvalue assignment problem (RPQEAP) with repeated prescribed eigenvalues. We first derive a result on the solution of partial quadratic eigenvalue assignment problem, which leads to the partial Schur form of the closed-loop system. Then by minimizing the normality departure of the partial Schur form of the closed-loop system, we assign the prescribed eigenvalues step by step such that the closed-loop system is as robust as possible. Our method allows the prescribed eigenvalues are repeated. Moreover, the proposed method does not use the unchanged eigenpairs of the open-loop system and avoids transforming the second-order control system to the first-order system. Numerical experiments show that the proposed method is efficient for solving the RPQEAP with repeated eigenvalues. [ABSTRACT FROM AUTHOR]

Harris Hawk optimization (HHO) is a new robust metaheuristic algorithm proposed for the solution of large intractable combinatorial optimization problems. The hawks are cooperative birds and use many intelligent hunting techniques. This study proposes new HHO algorithms for solving the well-known quadratic assignment problem (QAP). Large instances of the QAP have not been solved exactly yet. We implement HHO algorithms with robust tabu search (HHO-RTS) and introduce new operators that simulate the actions of hawks. We also developed an island parallel version of the HHO-RTS algorithm using the message passing interface. We verify the performance of our proposed algorithms on the QAPLIB benchmark library. One hundred and twenty-five of 135 problems are solved optimally, and the average deviation of all the problems is observed to be 0.020%. The HHO-RTS algorithm is a robust algorithm compared to recent studies in the literature. [ABSTRACT FROM AUTHOR]

The performance of optimization algorithms, and consequently of AI/machine learning solutions, is strongly influenced by the setting of their hyperparameters. Over the last decades, a rich literature has developed proposing methods to automatically determine the parameter setting for a problem of interest, aiming at either robust or instance-specific settings. Robust setting optimization is already a mature area of research, while instance-level setting is still in its infancy, with contributions mainly dealing with algorithm selection. The work reported in this paper belongs to the latter category, exploiting the learning and generalization capabilities of artificial neural networks to adapt a general setting generated by state-of-the-art automatic configurators. Our approach differs significantly from analogous ones in the literature, both because we rely on neural systems to suggest the settings, and because we propose a novel learning scheme in which different outputs are proposed for each input, in order to support generalization from examples. The approach was validated on two different algorithms that optimized instances of two different problems. We used an algorithm that is very sensitive to parameter settings, applied to generalized assignment problem instances, and a robust tabu search that is purportedly little sensitive to its settings, applied to quadratic assignment problem instances. The computational results in both cases attest to the effectiveness of the approach, especially when applied to instances that are structurally very different from those previously encountered. [ABSTRACT FROM AUTHOR]

We consider both facial reduction, FR, and symmetry reduction, SR, techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. In fact, this approach allows for simply adding on nonnegativity constraints, and solving the doubly nonnegative, DNN , relaxation of many classes of hard combinatorial problems. We also show that the singularity degree remains the same after SR, and that the DNN relaxations considered here have singularity degree one, that is reduced to zero after FR. The combination of FR and SR leads to a significant improvement in both numerical stability and running time for both the ADMM and interior point approaches. We test our method on various DNN relaxations of hard combinatorial problems including quadratic assignment problems with sizes of more than n = 500 . This translates to a semidefinite constraint of order 250, 000 and 625 × 10 8 nonnegative constrained variables, before applying the reduction techniques. [ABSTRACT FROM AUTHOR]

We present an effective spectral matching method based on a shape association graph for finding region correspondences between two cel animation keyframes. We formulate the correspondence problem as an adapted quadratic assignment problem, which comprehensively considers both the intrinsic geometric and topology of regions to find the globally optimal correspondence. To simultaneously represent the geometric and topological similarities between regions, we propose a shape association graph (SAG), whose node attributes indicate the geometric distance between regions, and whose edge attributes indicate the topological distance between combined region pairs. We convert topological distance to geometric distance between geometric objects with topological features of the pairs, and introduce Kendall shape space to calculate the intrinsic geometric distance. By utilizing the spectral properties of the affinity matrix induced by the SAG, our approach can efficiently extract globally optimal region correspondences, even if shapes have inconsistent topology and severe deformation. It is also robust to shapes undergoing similarity transformations, and compatible with parallel computing techniques. [ABSTRACT FROM AUTHOR]

Focusing on the dynamic improvement of the underlying service network configuration, this paper aims to address a specific challenge of redesigning a multi-echelon city logistics distribution network. By considering the intra-echelon connection of facilities within the same layer of echelon, we propose a new distribution network design model by reformulating the classical quadratic assignment problem (QAP). To minimize the overall transportation costs, the proposed model jointly optimizes two types of decisions to enable agile distribution with dynamic "shortcuts": (i) the allocation of warehouses to supply the corresponding distribution centers (DCs), and (ii) the demand coverage decision from distribution centers to delivery stations. Furthermore, a customized branch-and-bound algorithm is developed, where the lower bound is obtained by adopting Gilmore and Lawler lower Bound (GLB) for QAP. We conduct extensive computational experiments, highlighting the significant contribution of GLB-oriented lower bound, to obtain practical solutions; this type of efficient mathematical lower bounds offers a powerful tool for balancing theoretical research ideas with practical and industrial applicability. [ABSTRACT FROM AUTHOR]

A common computational approach for polynomial optimization problems (POPs) is to use (hierarchies of) semidefinite programming (SDP) relaxations. When the variables in the POP are required to be nonnegative – as is the case for combinatorial optimization problems, for example – these SDP problems typically involve nonnegative matrices, i.e. they are conic optimization problems over the doubly nonnegative cone. The Jordan reduction, a symmetry reduction method for conic optimization, was recently introduced for symmetric cones by Parrilo and Permenter [Mathematical Programming 181(1), 2020]. We extend this method to the doubly nonnegative cone, and investigate its application to known relaxations of the quadratic assignment and maximum stable set problems. We also introduce new Julia software where the symmetry reduction is implemented. [ABSTRACT FROM AUTHOR]

The discrete differential evolution (DDE) algorithm is an evolutionary algorithm (EA) that has effectively solved challenging optimization problems. However, like many other EAs, it still faces problems such as premature convergence and stagnation during the iterative process. To address these concerns in the DDE algorithm, this work aims to achieve the following objectives: (i) investigate the causes of premature convergence and stagnation in the DDE algorithm; (ii) propose techniques to prevent premature convergence and stagnation in DDE, including a quantitative measurement of premature convergence based on the level of mismatching between the population solutions and then divide the population into individual groups based on the level of mismatching between the population solutions and the best solution; and applying the roulette wheel selection (RWS) approach to determine whether a higher degree of nonmatching is more suitable for choosing a population of separate groups to be able to produce a new solution with more options to prevent the occurrence of premature convergence; (iii) evaluate the effectiveness of the proposed techniques through employing the DDE algorithm to solve the quadratic assignment problem (QAP) as a standard to evaluate our results and their effect on avoiding premature convergence and stagnation issues, which led to the enhancement of the algorithm's accuracy. Our comparative study based on the statistical analysis shows that the DDE algorithm that uses the proposed techniques is more efficient than the traditional DDE algorithm and the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

It is well-established that increased product visibility to shoppers leads to higher sales for retailers. In this study, we propose an optimization methodology which assigns product categories and subcategories to store locations and sublocations to maximize the overall visibility of products to shoppers. The methodology is hierarchically developed to meet strategic and tactical layout planning needs of brick-and-mortar retailers. Layouts in both levels of planning are optimized considering eligibility requirements and complete set of shopper paths, thus, they successfully capture the unique shopping behaviour of consumers in a store's region. The resulting mathematical optimization problem is recognized as a special instance of the well-known Quadratic Assignment Problem, which is considered computationally as one of the hardest optimization problems. We adopt a linearization technique and demonstrate via a real-world numerical example that our linearized optimization models substantially improve the store layout, hence, can be used in practical applications as a vital decision support model for store layout planning. [ABSTRACT FROM AUTHOR]

This paper presents a parallel evolutionary metaheuristic which includes different threads aimed at balancing exploration versus exploitation. Exploring different areas of the search space independently, each thread also communicates with other threads, and exploits the search space by improving a common high quality solution. The presented metaheuristic has been applied to three famous and hard-to-solve optimization problems, namely the job shop scheduling, the permutation flowshop scheduling, and the quadratic assignment problems. The results of computational experiments indicate that it is effective, versatile and robust, competing with the-state-of-art procedures presented for these three problems. In effect, in terms of solution quality, and average required running time to reach a high quality solution, the procedure outperforms several state-of-the-art procedures on multiple benchmark instances. [ABSTRACT FROM AUTHOR]

Identifying cause-effect relations among variables is a key step in the decision-making process. Whereas causal inference requires randomized experiments, researchers and policy makers are increasingly using observational studies to test causal hypotheses due to the wide availability of data and the infeasibility of experiments. The matching method is the most used technique to make causal inference from observational data. However, the pair assignment process in one-to-one matching creates uncertainty in the inference because of different choices made by the experimenter. Recently, discrete optimization models have been proposed to tackle such uncertainty; however, they produce 0-1 nonlinear problems and lack scalability. In this work, we investigate this emerging data science problem and develop a unique computational framework to solve the robust causal inference test instances from observational data with continuous outcomes. In the proposed framework, we first reformulate the nonlinear binary optimization problems as feasibility problems. By leveraging the structure of the feasibility formulation, we develop greedy schemes that are efficient in solving robust test problems. In many cases, the proposed algorithms achieve a globally optimal solution. We perform experiments on real-world data sets to demonstrate the effectiveness of the proposed algorithms and compare our results with the state-of-the-art solver. Our experiments show that the proposed algorithms significantly outperform the exact method in terms of computation time while achieving the same conclusion for causal tests. Both numerical experiments and complexity analysis demonstrate that the proposed algorithms ensure the scalability required for harnessing the power of big data in the decision-making process. Finally, the proposed framework not only facilitates robust decision making through big-data causal inference, but it can also be utilized in developing efficient algorithms for other nonlinear optimization problems such as quadratic assignment problems. History: Accepted by Ram Ramesh, Area Editor for Data Science and Machine Learning. Funding: This work was supported by the Division of Civil, Mechanical and Manufacturing Innovation of the National Science Foundation [Grant 2047094]. Supplemental Material: The online supplements are available at https://doi.org/10.1287/ijoc.2022.1226. [ABSTRACT FROM AUTHOR]

A new method is proposed for robust quadratic pole assignment problem. We first give the results on the solution of quadratic pole assignment problem. Then the Schur form corresponding to closed-loop system is established and normality departure is used to measure the robustness of closed-loop system. On these grounds, a method for robust quadratic pole assignment problem is proposed by minimizing the normality departure of closed-loop system. The proposed method avoids to transform the second-order control system to the first-order control system. Moreover, it is implemented in real operations. Numerical experiments show that our method has good performance on the robustness of closed-loop system. [ABSTRACT FROM AUTHOR]

Graph matching involves combinatorial optimization based on edge-to-edge affinity matrix, which can be generally formulated as Lawler's quadratic assignment problem (QAP). This paper presents a QAP network directly learning with the affinity matrix (equivalently the association graph) whereby the matching problem is translated into a constrained vertex classification task. The association graph is learned by an embedding network for vertex classification, followed by Sinkhorn normalization and a cross-entropy loss for end-to-end learning. We further improve the embedding model on association graph by introducing Sinkhorn based matching-aware constraint, as well as dummy nodes to deal with unequal sizes of graphs. To our best knowledge, this is one of the first network to directly learn with the general Lawler's QAP. In contrast, recent deep matching methods focus on the learning of node/edge features in two graphs respectively. We also show how to extend our network to hypergraph matching, and matching of multiple graphs. Experimental results on both synthetic graphs and real-world images show its effectiveness. For pure QAP tasks on synthetic data and QAPLIB benchmark, our method can perform competitively and even surpass state-of-the-art graph matching and QAP solvers with notable less time cost. We provide a project homepage at http://thinklab.sjtu.edu.cn/project/NGM/index.html. [ABSTRACT FROM AUTHOR]

Focusing on the dynamic improvement of the underlying service network configuration, this paper aims to address a specific challenge of redesigning a multi-echelon city logistics distribution network. By considering the intra-echelon connection of facilities within the same layer of echelon, we propose a new distribution network design model by reformulating the classical quadratic assignment problem (QAP). To minimize the overall transportation costs, the proposed model jointly optimizes two types of decisions to enable agile distribution with dynamic “shortcuts”: (i) the allocation of warehouses to supply the corresponding distribution centers (DCs), and (ii) the demand coverage decision from distribution centers to delivery stations. Furthermore, a customized branch-and-bound algorithm is developed, where the lower bound is obtained by adopting Gilmore and Lawler lower Bound (GLB) for QAP. We conduct extensive computational experiments, highlighting the significant contribution of GLB-oriented lower bound, to obtain practical solutions; this type of efficient mathematical lower bounds offers a powerful tool for balancing theoretical research ideas with practical and industrial applicability.

This article is devoted to solving the quadratic assignment problem using a hybrid algorithm contains both genetic and evolutionary algorithms. The quadratic assignment problem is one of the fundamental problems of combinatorial optimization in the field of mathematical optimization, belonging to the category of object placement problem. The article provides a simple statement of this problem and its more detailed mathematical model. Since the quadratic assignment problem is NP-hard and even small input data can take large computational costs for an accurate algorithm, it is reasonable to use a hybrid heuristic approach to solve this problem. The article describes in detail the construction of a hybrid algorithm, the sequence of its steps, and the flowchart. Further, the article provides a graphical interface with the ability to adjust various parameters of the algorithm, allowing it to be optimally configured. The last part of the article covers a comparative analysis of the effectiveness of the resulting algorithm: comparing the accuracy of the developed hybrid algorithm with a new method of invasive weed optimization algorithm, comparing it with the best-known solutions for modern benchmarks. It was found that the hybrid algorithm shows a strong advantage in accuracy over the invasive weed optimization algorithm. Also, the hybrid algorithm was able to find a solution equal to the best known for the tai12a problem. For the tai15a problem, the algorithm showed a deviation of 0.2% from the best-known solution. For the rest of the considered benchmarks, the algorithm showed a deviation from the best solutions of no more than 4.2%, which proves the high efficiency of the created algorithm in comparison with the world's best solutions. In addition, this algorithm has a high economic value due to the wide application of the solution to the problem in practice, for example, in placement of factories or enterprises in places or in placement of associated electronic components on printed circuit boards or integrated circuits, etc.

Ant Colony Optimization is a population metaheuristic inspired by the behavior of natural ants, specifically their ability to find the shortest path between their nest and the food source. This search mechanism has been tested in discrete problems, establishing itself as a good option for this field of application. In previous works, it was shown that dividing the exploration process of these algorithms into 2 stages considerably improves their performance in terms of time and the quality of the results. In this context, we present, in this work, a generalization of the exploitation process by stages for instances of the Medium and High-Dimension of the Traveling Salesman Problem. For the tests, 5 instances of different sizes were selected and 4 variants of the algorithm were analyzed. The results corroborated that the process of division into stages is good for the performance of the algorithm, reaching the best results with 4 stages. [ABSTRACT FROM AUTHOR]

Splitting methods in optimization arise when one can divide an optimization problem into two or more simpler subproblems. They have proven particularly successful for relaxations of problems involving discrete variables. We revisit and strengthen splitting methods for solving doubly nonnegative relaxations of the particularly difficult, NP-hard quadratic assignment problem. We use a modified restricted contractive splitting method approach. In particular, we show how to exploit redundant constraints in the subproblems. Our strengthened bounds exploit these new subproblems and new dual multiplier estimates to improve on the bounds and convergence results in the literature. Summary of Contribution: In our paper, we consider the quadratic assignment problem (QAP). It is one of the fundamental combinatorial optimization problems in the fields of optimization and operations research and includes many fundamental applications. We revisit and strengthen splitting methods for solving doubly nonnegative (DNN) relaxation of the QAP. We use a modified restricted contractive splitting method. We obtain strengthened bounds from improved lower and upper bounding techniques, and in fact, we solve many of these NP-hard problems to (provable) optimality, thus illustrating both the strength of the DNN relaxation and our new bounding techniques. [ABSTRACT FROM AUTHOR]

ELA features are used for identifying strengths and weaknesses of algorithms, automatic algorithm selection, per instance algorithm configuration and generation methods, and benchmark construction techniques. The extracted features of algorithms, their main concepts, and search operators, are used to create a set of classification indicators to distinguish between a representative set of algorithm behaviors. The paper I Understanding measure-driven algorithms solving irreversibly ill-conditioned problems i by Sawicki et al. provides a framework for understanding and analyzing the behavior of stochastic population-based algorithms in solving ill-conditioned global optimization problems. Understanding of optimization algorithm's behavior is a vital part that is needed for quality progress in the field of stochastic optimization algorithms. [Extracted from the article]